{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Meeting Rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canAttendMeetings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #会议室"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个会议时间安排的数组 <code>intervals</code> ，每个会议时间都会包括开始和结束的时间 <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> ，请你判断一个人是否能够参加这里面的全部会议。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[0,30],[5,10],[15,20]]\n",
    "<strong>输出</strong>：false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[7,10],[2,4]]\n",
    "<strong>输出</strong>：true\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= intervals.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>0 <= start<sub>i</sub> < end<sub>i</sub> <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [meeting-rooms](https://leetcode.cn/problems/meeting-rooms/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [meeting-rooms](https://leetcode.cn/problems/meeting-rooms/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,30],[5,10],[15,20]]', '[[7,10],[2,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        if len(intervals) < 2:\n",
    "            return True\n",
    "        start, end = list(zip(*intervals))\n",
    "        sorted_start = sorted(list(range(len(start))), key=lambda k: start[k])\n",
    "        for i in range(len(start)-1):\n",
    "            if start[sorted_start[i+1]] < end[sorted_start[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort(key=lambda l:l[1])\n",
    "        last_meeting_end_time = -1\n",
    "        for meeting in intervals:\n",
    "            if last_meeting_end_time != -1:\n",
    "                if meeting[0] < last_meeting_end_time:\n",
    "                    return False\n",
    "            last_meeting_end_time = meeting[1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        for x in range(1,len(intervals)):\n",
    "            for i in range(0, x):\n",
    "                if intervals[x][0] >= intervals[i][1]:\n",
    "                    continue\n",
    "                if intervals[x][1] <= intervals[i][0]:\n",
    "                    continue\n",
    "                return False\n",
    "        return True    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort()\n",
    "        i = 1\n",
    "        while i < len(intervals):\n",
    "            l1, r1 = intervals[i-1]\n",
    "            l2, r2 = intervals[i]\n",
    "            if r1 > l2:\n",
    "                return False\n",
    "            i += 1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals = sorted(intervals,key=lambda x:x[0])\n",
    "        for i in range(len(intervals)-1):\n",
    "            if intervals[i+1][0]<intervals[i][1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals = sorted(intervals,key=lambda x:x[0])\n",
    "        for i in range(len(intervals)-1):\n",
    "            if intervals[i+1][0]<intervals[i][1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canAttendMeetings(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        intervals = sorted(intervals, key = (lambda x: x[0]))\n",
    "        for i in intervals:\n",
    "            a.append(i[0])\n",
    "            a.append(i[1])\n",
    "        if a == sorted(a): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        if len(intervals)<2:\n",
    "            return True\n",
    "        intervals.sort(key=lambda x:(x[0],x[1]))\n",
    "        start,end = intervals[0][0],intervals[0][1]\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]<end:\n",
    "                return False\n",
    "            else:\n",
    "                end = intervals[i][1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort(key = lambda x: x[0])\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i - 1][1] > intervals[i][0]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        if not intervals: return True\n",
    "        intervals.sort()\n",
    "        pre = intervals[0]\n",
    "        for i in intervals[1:]:\n",
    "            if i[0] < pre[1]:\n",
    "                return False\n",
    "            pre = i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort()\n",
    "        for i in range(1,len(intervals)):\n",
    "            if intervals[i][0]<intervals[i-1][1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "    intervals.sort()\n",
    "    for c in range(1, len(intervals)):\n",
    "      if intervals[c][0] - intervals[c - 1][1] < 0:\n",
    "        return False\n",
    "    return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort()\n",
    "        prev = -1\n",
    "        for s, e in intervals:\n",
    "            if s < prev:\n",
    "                return False\n",
    "            prev = e\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        if not intervals:\n",
    "            return True\n",
    "\n",
    "        intervals.sort()\n",
    "        cur = None\n",
    "        for i in intervals:\n",
    "            if not cur:\n",
    "                cur = i[1]\n",
    "            else:\n",
    "                if i[0] < cur:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur = i[1]\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort(key=lambda interval:interval[0])\n",
    "        # print(intervals)\n",
    "        for i in range(1,len(intervals)):\n",
    "            if(intervals[i][0] < intervals[i-1][1]):return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort(key=lambda a : (a[0], a[1]))\n",
    "\n",
    "        for i in range(len(intervals) - 1):\n",
    "            if intervals[i][1] > intervals[i + 1][0]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort()\n",
    "        for i in range(len(intervals)-1 ):\n",
    "            if intervals[i][1] >intervals[i+1][0] and intervals[i][0] < intervals[i+1][1]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        r = -inf\n",
    "        intervals.sort()\n",
    "        for start, end in intervals:\n",
    "            if r > start:\n",
    "                return False\n",
    "            r = max(r, end)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        # 根据会议开始时间排序\n",
    "        intervals.sort(key=lambda x:x[0])\n",
    "        return all(intervals[i-1][1] <= intervals[i][0] for i in range(1, len(intervals)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        # 有重叠就无法都参加\n",
    "        if not intervals:\n",
    "            return True\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        pre_start, pre_end = intervals[0][0], intervals[0][1]\n",
    "        for cur_start, cur_end in intervals[1:]:\n",
    "            if pre_end > cur_start:\n",
    "                return False\n",
    "            pre_start, pre_end = cur_start, cur_end\n",
    "        return True\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "\n",
    "        n = len(intervals)\n",
    "\n",
    "        # Special case\n",
    "        if n == 0:\n",
    "            return True\n",
    "\n",
    "        intervals.sort(key = lambda x: (x[1], x[0]))\n",
    "\n",
    "        prev_end = intervals[0][1]\n",
    "        for interval in intervals[1:]:\n",
    "            if interval[0] < prev_end:\n",
    "                return False\n",
    "            prev_end = interval[1]\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        tuples = []\n",
    "        for interval in intervals:\n",
    "            tuples.append(tuple(interval))\n",
    "        tuples.sort(key=lambda a:a[0])\n",
    "        for i in range(len(tuples)-1):\n",
    "            cur_ending = tuples[i][1]\n",
    "            nxt_start = tuples[i+1][0]\n",
    "            if nxt_start < cur_ending:\n",
    "                return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        print(intervals)\n",
    "        \n",
    "\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] < intervals[i - 1][1]:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:\n",
    "        lst = []\n",
    "        START, END = 1, -1\n",
    "        for l, r in intervals:\n",
    "            lst.append((l, START))\n",
    "            lst.append((r, END))\n",
    "        lst.sort()\n",
    "        count = 0\n",
    "        for t, cmd in lst:\n",
    "            count += cmd\n",
    "            if count > 1:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
